#include <iostream>
#include <stack>

using namespace std;
// 设计求表达式值的类Express
class Express   // 求表达式值的类
{
    string exp;     // 存放中缀表达式
    string postexp; // 存放后缀表达式
public:
    Express(string str) // 构造函数
    {
        exp = str;
        postexp = "";
    }
    string getpostexp() // 返回后缀表达式postexp
    {
        return postexp;
    }
    void Trans()    // 将exp转换成postexp
    {
        stack<char> opor;   // 定义运算符栈opor
        int i = 0;  // i为exp的下标
        char ch, e;
        // exp表达式未扫描完时循环
        while(i < exp.length())
        {
            ch = exp.at(i);
            if(ch == '(')   // 遇到左括号
                opor.push(ch);  // 将左括号直接进栈
            else if(ch == ')')  // 遇到右括号
            {
                // 将栈中'('之前的运算符退栈并存入postexp
                while(!opor.empty() && opor.top() != '(')
                {
                    e = opor.top();
                    opor.pop();
                    postexp += e;
                }
                opor.pop(); // 将'('退栈
            }
            else if(ch == '+' || ch == '-')   // 遇到加或减号
            {
                while(!opor.empty() && opor.top() != '(')
                {
                    e = opor.top(); // 将栈中(之前的所有运算符退栈
                    opor.pop(); // 并存入postexp
                    postexp += e;
                }
                opor.push(ch);  // 再将'+'或‘-’进栈
            }
            else if(ch == '*' || ch == '/') // 遇到'*'或'/'号
            {
                while(!opor.empty() && opor.top() != '('
                && (opor.top() == '*' || opor.top() == '/'))
                {
                    e = opor.top(); // 将栈中(之前的素有*或/依次出栈
                    opor.pop();
                    postexp += e;
                }
                opor.push(ch);  // 再将'*'或'/'进栈
            }
            else    // 遇到数字字符
            {
                string d = "";  // 用于提取数字字符
                while(ch >= '0' && ch <= '9')   // 数字字符
                {
                    d += ch;    // 提取所有连续的数字字符
                    i++;
                    if(i < exp.length())    // exp没有遍历完时取下一个字符ch
                        ch = exp.at(i);
                    else
                        break;  //exp遍历完毕退出数字判断
                }

                postexp += d;   // 将数字串存入postexp
                postexp += '#';  // 用#标识一个数字串结束
                i--;    // 退一个字符（因为经过上面的while循环，i指向了一个非数字字符
            }
            i++;    // 继续处理其他字符
        }

        while(!opor.empty())    // 此时exp扫描完毕，栈不空时循环
        {
            e = opor.top();
            opor.pop(); // 将栈中所有运算符退栈并放入postexp
            postexp += e;
        }
    }
    double GetValue()   // 计算后缀表达式postexp的值
    {
        stack<double> opand;    // 定义运算数栈opand
        double a, b, c, d;
        char ch;
        int i = 0;
        while(i < postexp.length()) // postexp字符串为扫描完成时循环
        {
            ch = postexp.at(i);
            switch (ch) {
                case '+':   // 遇到+
                    a = opand.top(); opand.pop();   // 退栈运算数a
                    b = opand.top(); opand.pop();   // 退栈运算数b
                    c = b + a;  // 计算c
                    opand.push(c);  // 将计算结果进栈
                    break;
                case '-':
                    a = opand.top(); opand.pop();   // 退栈运算数a
                    b = opand.top(); opand.pop();   // 退栈运算数b
                    c = b - a;  // 计算c
                    opand.push(c);  // 将计算结果进栈
                    break;
                case '*':
                    a = opand.top(); opand.pop();   // 退栈运算数a
                    b = opand.top(); opand.pop();   // 退栈运算数b
                    c = b * a;  // 计算c
                    opand.push(c);  // 将计算结果进栈
                    break;
                case '/':
                    a = opand.top(); opand.pop();   // 退栈运算数a
                    b = opand.top(); opand.pop();   // 退栈运算数b
                    c = b / a;  // 计算c。没有考虑a为0的情况
                    opand.push(c);  // 将计算结果进栈
                    break;
                default:    // 遇到数字字符
                    d = 0;  // 将连续的数字字符转换为数值存放d中
                    while(ch >= '0' && ch <= '9')
                    {
                        d = 10 * d + (ch - '0');
                        i++;
                        ch = postexp.at(i); // 继续查看下一个字符
                    }
                    opand.push(d);  // 将数值d进栈
                    break;
            }
            i++;    // 继续处理其他字符
        }
        return opand.top(); //栈顶元素即为求值结果
    }
};
int main() {
    string str = "(56-20+3)/(4+2)";   // 定义一个中缀表达式
    Express obj(str);
    cout << "Infix expression:" << str << endl;
    cout << "Transfer Infix expression to Post expression" << endl;
    obj.Trans();
    cout << "Post expression:" << obj.getpostexp() << endl;
    cout << "GetValue:" << obj.GetValue() << endl;
    return 0;
}
